package recursion

import org.scalatest.{FunSpec, Matchers}

/**
 * Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
 *
 * k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
 *
 * Example:
 *
 * Given this linked list: 1->2->3->4->5
 * For k = 2, you should return: 2->1->4->3->5
 * For k = 3, you should return: 3->2->1->4->5
 */
class Q25ReverseNodesKGroup extends FunSpec with Matchers {

  def reverseKGroup(head: ListNode, k: Int): ListNode = {
    if (head != null) {
      val (_, kHead, next) = reverseK(head, k)
      if (kHead == null) head
      else {
        head.next = reverseKGroup(next, k)
        kHead
      }
    } else null
  }

  def reverseK(node: ListNode, depth: Int): (ListNode, ListNode, ListNode) = {
    println(s"${node}")
    if (node == null || (node.next == null && depth > 1)) (null, null, null)
    else if (depth == 1) (node, node, node.next)
    else {
      val (next, last, adj) = reverseK(node.next, depth - 1)
      if (next == null && last == null) (null, null, null)
      else {
        next.next = node
        (node, last, adj)
      }
    }
  }

  describe("reverse linked list") {

    it("recursive") {
      println(s"result: ${reverseKGroup(nodes(5), 2)}")
      println(s"result: ${reverseKGroup(nodes(5), 3)}")
      println(s"result: ${reverseKGroup(nodes(2), 2)}")
    }
  }

}